|
In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set ''S'' such that every edge of the graph has at least one endpoint not in ''S'' and every vertex not in ''S'' has at least one neighbor in ''S''. A MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets. A graph may have many MISs of widely varying sizes;〔 shows that the number of different sizes of MISs in an ''n''-vertex graph may be as large as ''n'' - log ''n'' - O(log log ''n'') and is never larger than ''n'' - log ''n''.〕 a largest MISs is called a maximum independent set. For example, in the graph P3, a path with three vertices ''a'', ''b'', and ''c'', and two edges ''ab'' and ''bc'', the sets and are both maximally independent. The set is independent, but is not maximal independent, because it is a subset of the larger independent set . In this same graph, the maximal cliques are the sets and . The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids. Two algorithmic problems are associated with MISs: finding a ''single'' MIS in a given graph and listing ''all'' MISs in a given graph. == Related vertex sets == If ''S'' is a maximal independent set in some graph, it is a maximal clique or maximal complete subgraph in the complementary graph. A maximal clique is a set of vertices that induces a complete subgraph, and that is not a subset of the vertices of any larger complete subgraph. That is, it is a set ''S'' such that every pair of vertices in ''S'' is connected by an edge and every vertex not in ''S'' is missing an edge to at least one vertex in ''S''. A graph may have many maximal cliques, of varying sizes; finding the largest of these is the maximum clique problem. Some authors include maximality as part of the definition of a clique, and refer to maximal cliques simply as cliques. The complement of a maximal independent set, that is, the set of vertices not belonging to the independent set, forms a minimal vertex cover. That is, the complement is a vertex cover, a set of vertices that includes at least one endpoint of each edge, and is minimal in the sense that none of its vertices can be removed while preserving the property that it is a cover. Minimal vertex covers have been studied in statistical mechanics in connection with the hard-sphere lattice gas model, a mathematical abstraction of fluid-solid state transitions.〔.〕 Every maximal independent set is a dominating set, a set of vertices such that every vertex in the graph either belongs to the set or is adjacent to the set. A set of vertices is a maximal independent set if and only if it is an independent dominating set. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Maximal independent set」の詳細全文を読む スポンサード リンク
|